I2P: Transparent implementation of EdDSA signature

Recently, the electronic signature Ed25519, based on a type of elliptic curve proposed by Bernstein, has become increasingly popular. As the number of I2P nodes with this type of signature increased, it became necessary to support it in their I2P implementation, since Ed25519 is not included in popular cryptographic libraries. As a rule, ref10 varieties from the library are used SUPERCOP, implemented by Bernstein himself in assembler, and then ported to other languages. This implementation works well and quickly, but it has a major drawback - it is not clear. Indeed, if you look into the source code, you can see a large number of similar lines operating with many “magic” numbers, but it is not possible to understand what they mean without delving into the theory. The goal of this article is a mathematically transparent implementation of Ed22519, using only standard large number operations found in any cryptography library, at a speed sufficient for practical use in I2P.

How elliptic cryptography works

An implicit equation of a special type of plane curve called an elliptic curve is specified. A prime number is specified, forming a field of modulo residues. The coordinates of the curve points belong to this field, i.e. are non-negative integers not exceeding the modulus. An addition operation is specified on two points on the curve so that the new point also belongs to the curve. If you add a point to itself, you get multiplication by 2, if you add it again, then by 3, and so on, multiplication by an arbitrary number n. Also, along with the curve, a base point belonging to the curve is specified, operations on which are used in cryptography.

For cryptography, an arbitrary large number n is selected, which is the secret key, the base point is multiplied by it and the new point serves as the public key, which is then multiplied by the opposite side by another number for the purpose of key agreement or signature verification. Resilience is based on the current lack of a known method for determining the multiplier by point in a reasonable time

ed25519

Bershtein proposed using an elliptic curve with the following parameters.
Curve Equation:
, Where
Module:
q =
hence the name of the curve.

Base point:
(x, 4/5), where x is obtained by solving the equation (see below)
Its coordinates in explicit form:
x=15112221349535400772501151409588531511454012693041857206046113283949847762202,
y=46316835694926478169428394003475163141307993866256225615783033603165251855960.

Addition:
, Where

It should be noted that the division here is not the usual division with a remainder, but multiplication by the inverse modulus element, calculated according to Fermat's little theorem according to the formula , i.e., the operation of exponentiation modulo.

It is proposed to use only the coordinate as a public key y, if necessary, solving the equations of the curve for x, and calculating it using the formula .

Because the q representable in the form 8*K+5, then to calculate the square root of X you should use the formula . Indeed q = = , hence the square root .

Implementation

The code is completely located on by the address in the Signature.cpp file. Library functions are used to work with large numbers BN from openssl.
Let's create a class Ed25519 that implements the curve itself and contains the curve parameters calculated in its constructor. First of all, 3 methods are needed: addition, multiplication by a number and calculating x from a given y.

class Ed25519
{
//... 
    EDDSAPoint Sum (const EDDSAPoint& p1, const EDDSAPoint& p2) const
    EDDSAPoint Mul (const EDDSAPoint& p, const BIGNUM * e) const
    BIGNUM * RecoverX (const BIGNUM * y) const
//...
}

Due to the particular use of the addition operation and the complexity of the division operation, we reduce x and y to a common denominator (1+m)*(1-m), thereby getting rid of one division. As a result, the code for addition looks something like this:

// m = d*p1.x*p2.x*p1.y*p2.y
BN_mul (xx, p1.x, p2.x, m_Ctx); //p1.x*p2.x
BN_mul (yy, p1.y, p2.y, m_Ctx);  //p1.y*p2.y
BIGNUM * m = BN_dup (d);
BN_mul (m, m, xx, m_Ctx);
BN_mul (m, m, yy, m_Ctx);
// x = (p1.x*p2.y + p2.x*p1.y)*inv(1 + m)
// y = (p1.y*p2.y + p1.x*p2.x)*inv(1 - m)
// m1 = 1-m
BN_one (m1);
BN_sub (m1, m1, m);
// m = m+1
BN_add_word (m, 1);		
// y = (p1.y*p2.y + p1.x*p2.x)*m	
BN_add (y, xx, yy);
BN_mod_mul (y, y, m, q, m_Ctx);
// x = (p1.x*p2.y + p2.x*p1.y)*m1
BN_mul (yy, p1.x, p2.y, m_Ctx);
BN_mul (xx, p2.x, p1.y, m_Ctx);
BN_add (x, xx, yy);
// denominator m = m*m1	
BN_mod_mul (m, m, m1, q, m_Ctx);
Inv (m); 	
BN_mod_mul (x, x, m, q, m_Ctx); // x = x/m
BN_mod_mul (y, y, m, q, m_Ctx); // y = y/m

Also, for doubling (adding a point to itself), a separate Double method is implemented, since in this case p1.x = p2.x and p1.y = p2.y, which allows you to reduce the number of multiplications. In addition, the faster BN_sqr is used instead of BN_mul.
Multiplication released using the simplest method doubling and adding, those. go along the number bitwise from high to low, at each step double the value of the result, and if the bit is one, then add the point to be multiplied.

EDDSAPoint res {zero, one};
if (!BN_is_zero (e))
{
    int bitCount = BN_num_bits (e);
    for (int i = bitCount - 1; i >= 0; i--)
    {
        res = Double (res);
        if (BN_is_bit_set (e, i)) res = Sum (res, p);
    }
}	

Computing x from y is trivial.
First the radical expression:

BN_sqr (y2, y, m_Ctx); // y^2
// xx = (y^2 -1)*inv(d*y^2 +1) 
BN_mul (xx, d, y2, m_Ctx);
BN_add_word (xx, 1);
Inv (xx);
BN_sub_word (y2, 1);
BN_mul (xx, y2, xx, m_Ctx);

Then calculate the square root using the formula

// x = srqt(xx) = xx^(2^252-2)		
BN_mod_exp (x, xx, two_252_2, q, m_Ctx);

Signature and signature verification

This topic is quite interesting and extensive, so this issue will be devoted to separate article. At the same time, the Sign and Verify methods are implemented and used practically. Because if anyone is interested, you can look at the code. Here we will only list some features.
Like other electronic signature systems, the EdDSA signature is a pair of 32-byte numbers (R, S), therefore the length of the signature is 64 bytes.
Numbers presented in Little Endian.
SHA is used as a hash function-512.
When signing, a random number is not generated; instead, the right half of the SHA-512 hash of the secret key is used, combined with the data being signed..
Prime number is also used , used when choosing a base point, so that multiplying the base point by it would give zero.

Conclusion

Obviously, the slowest part of this implementation is the division in the addition operation. In fact, using modern advances in number theory and the specific parameters of EdDSA, it is possible to exclude it completely, as was done in ref10. However, this will significantly complicate the implementation and make it less understandable, so this should only be done if there is a real practical need. Currently, EdDSA signature verification in I2P is quite a rare event, compared to, say, ElGamal encryption.

There is an opinion that implementing your own cryptography is an extremely bad idea. However, using an implementation that is not clear as a working one seems to be little better. In addition, this article may be useful to those who are interested in getting to the bottom of it, and working practical code will help with this.